A network processor generally controls the flow of packets between a physical transmission medium, such as a physical layer portion of, e.g., an asynchronous transfer mode (ATM) network or synchronous optical network (SONET), and a switch fabric in a router or other type of packet switch. Such routers and switches generally include multiple network processors, e.g., arranged in the form of an array of line or port cards with one or more of the processors associated with each of the cards.
As is known, packet data that is to be processed by such network processors is maintained, at least temporarily, in one or more packet queues. Such packet data may include actual packets received by the packet switch or pointers to packets stored elsewhere. When packet data is needed for processing, the network processor obtains the packet data from the appropriate packet queue. However, due to the fact that the network processor may be forwarding the packet data to a device with limited processing capabilities (or a device that is bandwidth-restricted as a function of a service level agreement) and that, thus, requires transmission of the data to be carefully controlled, there is a need for a mechanism to control the stopping and restarting, i.e., delaying, of the transmission of packet data from the packet queues. One commonly used such delaying mechanism is known as a timeout table.
A timeout table is a data structure that maintains a set of timers. Timers are used to determine when “timeouts” occur, i.e., when a timer expires or a timeout value has been reached, indicating that a predetermined amount of time has passed and that therefore an action or processor function should be performed (i.e., begin or restart transmission of packet data from a packet queue to a network processor or some other device). Problems occur in the form of timeout errors (e.g., a timer expiring too late for a particular processor function), when a large amount of timers must be maintained.
One conventional form of timeout table is known as a one dimensional timeout table. Such a timeout table maintains a one dimensional list of entities (e.g., queues) that must be timed out at different times. However, such a table can be very large (consuming large amounts of memory), particularly when both small and large delays must be supported. In addition, there can be pathological jitter issues when entries having very different delays (i.e., delays having comparatively large time differences between them) happen to be placed in the same or in many adjacent slots of the one dimensional table.
Another conventional form of timeout table is known as a two dimensional timeout table. Such a timeout table maintains a list of groups, and within each group is a list of bins, wherein each bin has entities with different delays or timeout values associated therewith. While the two dimensional approach minimizes the memory space penalty of the one dimensional approach, the two dimensional data structure can cause an increase in the occurrence of timeout errors. Also, the two dimensional timeout table can experience significant congestion for the smallest delays due to the range of delays associated with entities stored in a single bin.
Accordingly, a need exists for improved timeout table mechanisms.